package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @author jzx
 * @date 2022/5/16
 * @desc https://leetcode.cn/problems/generate-parentheses/
 */
public class 括号生成 {

    public List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList();
        backTrack(res,n,n);
        return res;
    }


    StringBuilder  sb = new StringBuilder();
    public void backTrack(List<String> res,int leftCount,int rightCount){
        if(leftCount>rightCount) return;
        if(leftCount<0 || rightCount <0) return;
        if(leftCount == 0 && rightCount ==0){
            res.add(sb.toString());
            return;
        }

        sb.append("(");
        backTrack(res,leftCount-1,rightCount);
        sb.deleteCharAt(sb.length()-1);

        sb.append(")");
        backTrack(res,leftCount,rightCount-1);
        sb.deleteCharAt(sb.length()-1);
    }
}
